Networked Fairness in Cake Cutting

摘要

We introduce a graphical framework for fair division in cake cutting, wherecomparisons between agents are limited by an underlying network structure. Wegeneralize the classical fairness notions of envy-freeness and proportionalityto this graphical setting. Given a simple undirected graph G, an allocation isenvy-free on G if no agent envies any of her neighbor's share, and isproportional on G if every agent values her own share no less than the averageamong her neighbors, with respect to her own measure. These generalizationsopen new research directions in developing simple and efficient algorithms thatcan produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm thatoutputs an envy-free allocation on trees. The algorithm is significantlysimpler than the discrete and bounded envy-free algorithm recently designed byAziz and Mackenzie for complete graphs. Next, we give a discrete and boundedalgorithm for computing a proportional allocation on descendant graphs, a classof graphs by taking a rooted tree and connecting all its ancestor-descendantpairs.